package gold.digger;

import gold.vo.TreeNode;

import java.util.*;


/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC297 {
    public long startExecuteTime = System.currentTimeMillis();


    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder data = new StringBuilder();
            Deque<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode cur = root;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (null == cur) {
                    data.append(",null");
                    continue;
                }

                data.append("," + cur.val);
                queue.offer(cur.left);
                queue.offer(cur.right);
            }

            String treeVal = data.toString();
            int len = treeVal.length();
            while (len > 5 && treeVal.substring(len - 5, len).equals(",null")) {
                treeVal = treeVal.substring(0, len - 5);
                len -= 5;
            }
            return treeVal.substring(1);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            return createTree(data);
        }


        /**
         * 创建tree的工具之源
         *
         * @param order
         * @return
         */
        public TreeNode createTree(String order) {
            if (order.startsWith("[")) order = order.substring(1, order.length() - 1);
            List<String> levelList = Arrays.asList(order.split(","));

            if (levelList == null || levelList.isEmpty() || levelList.get(0).equals("null")) {
                return null;
            }

            TreeNode root = new TreeNode(Integer.parseInt(levelList.get(0)));
            Deque<TreeNode> preLayer = new LinkedList<>();
            Deque<TreeNode> curLayer = new LinkedList<>();
            int curLayerSize = 2;

            TreeNode curNode;
            preLayer.addLast(root);

            int currentIdx = 1;
            int len = levelList.size();
            while (currentIdx < len) {
                curLayerSize = preLayer.size() * 2;
                TreeNode father = preLayer.pollFirst();
                int nextFatherFlag = 0;
                for (int i = 0; i < curLayerSize && currentIdx + i < len; i++) {
                    String curNodeVal = levelList.get(currentIdx + i);
                    if ("null".equals(curNodeVal)) curNode = null;
                    else curNode = new TreeNode(Integer.parseInt(curNodeVal));

                    if (i % 2 == 0) father.left = curNode;
                    else father.right = curNode;

                    if (null != curNode) curLayer.addLast(curNode);
                    if (++nextFatherFlag > 1) {
                        nextFatherFlag = 0;
                        father = preLayer.pollFirst();
                    }
                }

                preLayer = curLayer;
                curLayer = new LinkedList<>();
                currentIdx += curLayerSize;
            }

            return root;
        }
    }


    public void run() {
        Codec solution = new Codec();
        TreeNode root = solution.deserialize("[5,2,3,null,null,2,4,3,1]");

        String rootVal = solution.serialize(root);
        System.out.println(rootVal);
        TreeNode deserializeRoot = solution.deserialize(rootVal);
        System.out.println(deserializeRoot);
    }

    public static void main(String[] args) throws Exception {
        LC297 an = new LC297();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
